//
//  39.平衡二叉树.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/27.
//

import Foundation
/*
 题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
        在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
        平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 思路：分治思想
 */
func offer_39() {
    let root = BinaryTreeNode(4)
    root.leftNode = {
        let node = BinaryTreeNode(2)
        node.leftNode = BinaryTreeNode(1)
        node.rightNode = BinaryTreeNode(3)
        return node
    }()
    root.rightNode = {
        let node = BinaryTreeNode(6)
        node.leftNode = BinaryTreeNode(5)
        node.rightNode = BinaryTreeNode(7)
        return node
    }()
    print(Solution().IsBalanced_Solution(root))
}

fileprivate class Solution {
    func IsBalanced_Solution(_ pRoot: BinaryTreeNode<Int>?) -> Bool {
        func depth(_ pRoot: BinaryTreeNode<Int>?) -> Int {
            guard pRoot != nil else { return 0 }
            let leftDepth = depth(pRoot?.leftNode)
            if leftDepth == -1 { return -1 }
            let rightDepth = depth(pRoot?.rightNode)
            if rightDepth == -1 { return -1 }
            let sub = abs(leftDepth - rightDepth)
            if sub > 1 { return -1 }
            return max(leftDepth, rightDepth) + 1
        }
        guard pRoot != nil else { return true }
        return depth(pRoot) != -1
    }
}

